n086  1858  18 Nov 84
BC-MATH
Eds, explanation of method in Addatend, but may be inserted in lede
anywhere after 9thgraf.
By JAMES GLEICK
c.1984 N.Y. Times News Service
    NEW YORK - A 28-year-old mathematician at AT&T Bell Laboratories has
made a startling theoretical breakthrough in the solving of systems
of equations that often grow too vast and complex for the most
powerful computers.
    The discovery, which is to be formally published next month, is
already circulating rapidly through the mathematical world. It has
also set off a deluge of inquiries from brokerage houses, oil
companies and airlines, industries with millions of dollars at stake
in problems known as linear programming.
    These problems are fiendishly complicated systems, often with
thousands of variables. They arise in a variety of commercial and
government applications ranging from allocating time on a
communications satellite to routing millions of telephone calls over
long distances, or whenever time must be allocated most efficiently
among competing users. Investment companies use them to devise
portfolios with the best mix of stocks and bonds.
    The Bell Labs mathematician, Dr. Narendra Karmarkar, has devised a
radically new procedure that may speed the routine handling of such
problems by businesses and government agencies and also make it
possible to tackle problems that are now far out of reach.
    ''This is a path-breaking result,'' said Dr. Ronald L. Graham,
director of mathematical sciences for Bell Labs in Murray Hill, N.J.
''Science has its moments of great progress, and this may well be one
of them.''
    Because problems in linear programming can have billions or more
possible answers, even high-speed computers cannot check every one.
So computers must use a special procedure, an algorithm, to examine
as few answers as possible before finding the best one - typically
the one that minimizes cost or maximizes efficiency.
    A procedure devised in 1947, the simplex method, is now used for
such problems, usually in the form of highly refined computer codes
sold by the International Business Machines Corp., among others.
    The new Karmarkar approach exists so far only in rougher computer
code. Its full value will be impossible to judge until it has been
tested experimentally on a wide range of problems. But those who have
tested the early versions at Bell Labs say that it already appears
many times faster than the simplex method, and the advantage grows
rapidly with more complicated problems.
    ''The problems that people would really like to solve are larger
than can be done today,'' Karmarkar said. ''I felt strongly that
there must be a better solution.''
    American Airlines, among others, has begun working with Karmarkar to
see whether his technique will speed their handling of linear
programming problems, from the scheduling of flight crews to the
planning of fuel loads. Finding the best answer to the fuel problem,
where each plane should refuel and how much it should carry, cuts
fuel costs substantially.
    ''It's big dollars,'' said Thomas M. Cook, American's director of
operations research. ''We're hoping we can solve harder problems
faster, and we think there's definite potential.''
    The Exxon Corp. uses linear programming for a variety of
applications, such as deciding how to spread its crude oil among
refineries. It is one of several oil companies studying the Karmarkar
algorithm.
    ''It promises a more rapid solution of linear programming
problems,'' said David Smith of Exxon's communications and computer
sciences department. ''It's most important at times when conditions
are changing rapidly, for example, the price of crude oil.''
    If Karmarkar's procedure performs as well as expected, it will be
able to handle many linear programming problems faster than the
simplex method can, saving money by using less computer time. But it
may also be applied to problems that are left unsolved now because
they are too big and too complex to tackle with the simplex method.
    For example, AT&T believes the discovery may provide a new approach
to the problem of routing long-distance telephone calls through
hundreds or thousands of cities with maximum efficiency. Because of
the different volumes of calls between different places, the
different capacities of the telephone lines and the different needs
of users at different hours, the problem is extraordinarily difficult.
    -
    Valuable though it may be, like some other discoveries that have
come out of the American Telephone and Telegraph Co.'s research
laboratory in the past, the Karmarkar algorithm may not be salable in
itself. An algorithm cannot be patented or copyrighted, although
specific computer code can be. Bell Labs is one of several companies
that are working on putting it into code.
    ''A creation of pure thought cannot be protected,'' said Graham at
Bell Labs. ''There will be a whole industry spawned by this as people
get a better idea of what's going on.''
    -
    Karmarkar, the son and nephew of mathematicians, was born in
Gwalior, India, and grew up in Poona, near Bombay. He joined Bell
Labs last year after attending the California Institute of Technology
at Pasadena and getting his doctorate from the University of
California at Berkeley.
    News of his discovery has been spreading through the computer
science community in preprinted copies of Karmarkar's paper and in
informal seminars. His paper is to be formally published in the
journal Combinatorica next month and will be a central topic at the
yearly meeting of the Operations Research Society of America this
week in Dallas.
    ''I've sensed a lot of excitement in the field,'' said Dr. Joseph F.
Traub, chairman of Columbia University's computer science department.
    
nyt-11-18-84 2155est
***************

n087  1907  18 Nov 84
BC-MATH Addatend
NYT NEW YORK: science department.
    Mathematicians visualize such problems as complex geometric solids
with millions or billions of facets. Each corner of each facet
represents a possible solution. The task of the algorithm is to find
the best solution, say the corner at the top, without having to
calculate the location of every one.
    The simplex method, devised by the mathematician George B. Dantzig
in 1947, in effect runs along the edges of the solid, checking one
corner after another but always heading in the direction of the best
solution. In practice it usually manages to get there efficiently
enough for most problems, as long as the number of variables is no
more than 15,000 or 20,000.
    The Karmarkar algorithm, by contrast, takes a giant short cut,
plunging through the middle of the solid. After selecting an
arbitrary interior point, the algorithm warps the entire structure -
in essence, reshaping the problem - in a way designed to bring the
chosen point exactly into the center. The next step is to find a new
point in the direction of the best solution and to warp the structure
again, bringing the new point into the center.
    ''Unless you do this warping,'' Karmarkar said, ''the direction that
appears to give the best improvement each time is an illusion.''
    The repeated transformations, based on a technique known as
projective geometry, lead rapidly to the best answer. Computer
scientists who have examined the method describe it as ingenious.
    ''It is very new and surprising - it has more than one theoretical
novelty,'' said Laszlo Babai, visiting professor of computer science
at the University of Chicago. ''The real surprise is that the two
things came together, the theoretical breakthrough and the practical
applicability.''
    Dantzig, now professor of operations research and computer science
at Stanford University, cautioned that it was too early to assess
fully the usefulness of the Karmarkar method. ''We have to separate
theory from practice,'' he said. ''It is a remarkable theoretical
result and it has a lot of promise in it, but the results are not all
in yet.''
    Many mathematicians interested in the theory of computer science
have long been dissatisfied with the simplex method, despite its
enormous practical success. This is because the program performs
poorly on problems designed specificaly to test its weaknesses,
so-called worst possible case problems.
    These problems tend to shed light on the most fundamental issues of
solvability. Business users, however, are most concerned with how
well an algorithm performs on the average, and how well it handles
the kinds of problems that tend to crop up in the real world.
    Mathematicians designed problems to frustrate the simplex method,
forcing it to step from corner to corner until it had examined all or
most of the possible solutions. From a practical point of view, that
made the problem unsolvable.
    But fortunately for computer science, the worst-case problems almost
never arise in the real world. ''You had to work hard to produce
these examples,'' Graham said. And the simplex method performs far
better on average than its worst-case limit would suggest.
    -
    Five years ago, a group of Soviet mathematicians devised a new
algorithm, the ellipsoid method, that handled those worst-case
problems far better than the simplex method. It was a theoretical
advance - but the ellipsoid had little practical significance because
its average performance was not much better than its worst-case
performance.
    The Soviet discovery, however, stimulated a burst of activity on the
problem and led to Karmarkar's breakthrough. The new algorithm does
far better in the worst case, and the improvement appears to apply as
well to the kinds of problems of most interest to industry.
    ''For a long time the mind-set that the simplex method was the way
to do things may have blocked other methods from being tested,'' said
Dr. Richard Karp, professor of computer science at the University of
California at Berkeley. ''It comes as a big surprise that what might
have been just a curiosity, like the ellipsoid, turns out to have
such practical importance.''
    
nyt-11-18-84 2204est
***************